leetcode

2023-03-31 21:24| 来源: 网络整理| 查看: 265

题目来自LeetCode，链接：two-sum。具体描述为：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

一个很容易想到的思路就是暴力法，遍历所有可能的两个数的组合，这样的时间复杂度为 O ( n 2 ) O(n^{2}) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1)。

当然上面的方法时间复杂度太高了，完全可以用更低时间复杂度的来做。因为题目假设只有一个答案，也就是说我们遍历一次数组肯定就可以得到一个答案，所以可以在 O ( n ) O(n) O(n)时间复杂度下完成。具体做法就是利用一个map保存{数->索引}的信息，遍历过程中对于当前遍历到的数，我们查看当前数是否在map中，不在的话我们把（target-当前数）作为key，当前索引作为value保存到map中去；在的话就说明当前数是之前某个数需要的那个残差数（target-之前那个数），因此我们找到了两个符合要求的数，取出在map中的value就是第一个数的索引，与当前索引构成了最终答案。分析一下可以知道这种方法需要额外空间来保存map，最多需要保存 n − 1 n-1 n−1个键值对信息，所以空间复杂度为 O ( n ) O(n) O(n)，可以看做用空间换时间的一种做法。

JAVA版代码如下：

class Solution { public int[] twoSum(int[] nums, int target) { Map num2residual = new HashMap(); for (int i = 0; i < nums.length; ++i) { if (num2residual.containsKey(nums[i])) { return new int[] {num2residual.get(nums[i]), i}; } else { num2residual.put(target - nums[i], i); } } return null; } }

提交结果如下:

Python版代码如下：

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: num2residual = {} for i in range(len(nums)): if nums[i] in num2residual: return [num2residual[nums[i]], i] else: num2residual[target - nums[i]] = i return None

提交结果如下:

【本文地址】

公司简介

联系我们